package leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:100. 相同的树
 * 时间复杂度：O(min(m,n))
 * 深度优先搜索
 * User: 东莞呵呵
 * Date:2022-07-20
 * Time:9:34
 */
public class TestDemo2 {
    //错误答案，不能判断逻辑结构是否相同，只能判断值
    /*public boolean isSameTree(TreeNode p, TreeNode q) {
        HashSet<Integer> set = new HashSet<>(preOrder(p));
        List<Integer> list=preOrder(q);
        for (int i = 0; i < list.size(); i++) {
            if(!set.contains(list.get(i))){
                return false;
            }
        }
        return true;
    }


    public List<Integer> preOrder (TreeNode root){
        List<Integer> list=new ArrayList<>();
        if(root==null){
            return list;
        }
        list.add(root.val);
        list.addAll(preOrder(root.left));
        list.addAll(preOrder(root.right));
        return list;
    }*/

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null){
            return true;
        }
        if(p==null||q==null){
            return false;
        }
        //不能判断相同时返回true
        if(p.val!=q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

